This invention relates to IP networks and, more particularly, to techniques for sequencing configuration changes in a network of IP routers.
Current IP networks are typically made up of routers that are interconnected by links. A packet sent to the network reaches a particular destination by specifying the IP address of a destination port. A packet reaches the desired destination port by being routed sequentially through a number of routers.
An OSPF domain of an IP network can be logically divided into a collection of Area Border Routers (ABRs) that are interconnected via xe2x80x9cbackbonexe2x80x9d links, with one or more Areas. Each Area comprises a subnetwork of routers that are interconnected by links. Within an Area there can also be subnets, and each subnet is a collection of interconnected IP routers with a gateway that interfaces the subnet to the rest of the network.
IP routers have numerous parameters that affect their operation. For example, routers can be set to provide a requested level of service, can be set to enhance the security of the communication, can be set to block communication from various sources, can be set to provide management information, etc. Of course, routers need to also carry out their primary mission of routing packets, and to do so routers run a routing protocol. As part of this protocol, each of the routers must develop a sense of the connectivity of the IP network within which it operates, and create a routing table to guide the routing of packets through the router. The routing protocol operates pursuant to various parameters that are associated with the routing protocol. As with the previously mentioned parameters, the routing protocol parameters are configured (e.g., updated) to the routers by one or more system administrators.
To perform the configuring or updating, administrators access routers through either Out-of-band or In-band channels. Out-of-band configuring is accomplished through the console of the router, or remotely through either a modem port of the router or a separate Ethernet port of the router. In-band configuring is accomplished by reaching the router via the network itself, i.e., by xe2x80x9ctelnetingxe2x80x9d to the router. In-band configuring is the most common method of access, because it does not require use of a separate access network.
Configuring routers from a central configuring site through the in-band channel presents a potential problem that stems from the fact that updating the parameters of a router can cause another router to be inaccessible. The problem is only a potential problem, because it can occur only when parameters that affect reachability of ports are updated, and only when the updating happens to be done in the wrong sequence. Consequently, it is important to properly sequence to updating of routers to avoid creating a situation where a router needs to be updated from the central site but is inaccessible to the central site.
Updating of routers is achieved by insuring that the scheduling of router updates is such that a zone of turbulence that occurs where the updating takes place does not prevent reaching any router that may be in need of updating. For IP routers that have a task scheduling capability, this is achieved by estimating the time for communicating update information to all routers that need to be updated, adding that estimate to time of day, and transmitting the update specifications. The routers receive the update specifications, schedule the update task, and independently update themselves at the appropriate time. In arrangements where routers do not have a task scheduling capability, updating is sequenced. Three methods are disclosed. One embodiment creates a set of traceroute trees that cover the nodes to be updated, and leaf nodes of the trees are taken up at random. All leaf nodes that are accounted for are removed from the trees, leaving nodes that were intermediate nodes of other trees. When such nodes become the only remaining leaf nodes, they are removed, and the process continues until no nodes remain in any of the trees. The second embodiment is more tree centric, in that once a starting node is identified (and its associated tree), all of its nodes are considered before progressing to another tree. The third embodiment takes advantage of the fact that if a node to be updated in not reachable when its updating is to be done, a second try that follows a delay is likely to succeed.